﻿// nQueen.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
using namespace std;

#define N 8
class Broad
{
public:
	void Init()
	{
		for (size_t i = 0; i < N; i++)
		{
			for (size_t j = 0; j < N; j++)
			{
				data[i][j] = '.';
			}
		}
	}

	void Show()
	{
		cout << "================= queen area ===============" << endl;
		for (size_t i = 0; i < N; i++)
		{
			for (size_t j = 0; j < N; j++)
			{
				cout << data[i][j] << " ";
			}
			cout << endl;
		}
	}

	void Play()
	{
		Place(0);
	}

private:
	void Place(int level)
	{
		if (level >= N)
		{
			Show();
			return;
		}

		for (size_t i = 0; i < N; i++)
		{
			if (!IsValid(level, i))
			{
				continue;
			}
			data[level][i] = 'Q';
			Place(level + 1);
			data[level][i] = '.';
		}
	}

	bool IsValid(int x, int y)
	{
		if (x == 0)
		{
			return true;
		}
		for (int i = 0; i < x; i++)
		{
			if (data[i][y] == 'Q'		// up
				|| (y - x + i > 0 && data[i][y - x + i] == 'Q')	// up left
				|| (y + x - i < N && data[i][y + x - i] == 'Q')	// up right
				)
			{
				return false;
			}
		}
		return true;
	}

private:
	char data[N][N];
};

class BroadArray
{
public:
	void Init()
	{
		for (size_t i = 0; i < N; i++)
		{
			data[i] = -1;
		}
	}

	void Show()
	{
		cout << "================= queen area ===============" << endl;
		for (size_t i = 0; i < N; i++)
		{
			for (size_t j = 0; j < N; j++)
			{
				if (data[i] == j)
				{
					cout << "Q" << " ";
				}
				else
				{
					cout << "." << " ";
				}
				
			}
			cout << endl;
		}
	}

	void Play()
	{
		Place(0);
	}

private:
	void Place(int level)
	{
		if (level >= N)
		{
			Show();
			return;
		}

		for (size_t i = 0; i < N; i++)
		{
			if (!IsValid(level, i))
			{
				continue;
			}
			data[level] = i;
			Place(level + 1);
			data[level] = -1;
		}
	}

	bool IsValid(int x, int y)
	{
		if (x == 0)
		{
			return true;
		}
		for (int i = 0; i < x; i++)
		{
			if (data[i] == y				// up
				|| (y - x + i > 0 && data[i] == y - x + i)	// up left
				|| (y + x - i < N && data[i] == y + x - i)	// up right
				)
			{
				return false;
			}
		}
		return true;
	}

private:
	char data[N];
};
int main()
{
	Broad b;

	b.Init();

	b.Play();

	return 0;
}
